package lec19graph.part1distance;

public class FloydDemo {
    private static final int INF = Integer.MAX_VALUE / 2;
    static int w[][]; // 边的价值，w[from][to]
    static int n = 4, m; // m为边数，n为顶点数

    public static void main(String[] args) {
        w = new int[][]{
                {0, 2, 6, 4},
                {INF, 0, 3, INF},
                {7, INF, 0, 1},
                {5, INF, 12, 0},
        };


        floyd();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(w[i][j] + " ");
            }
            System.out.println();
        }


    }

    private static void floyd() {//动态规划 O(n^3) 计算出任意两个点之间的最短路径
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (w[i][k] < INF && w[k][j] < INF)
                        w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);
                }
            }
        }
    }
}
